定律定義
Lucas定理:我們令 n=sp+q , m=tp+r . (q ,r ≤p)
那么:
(在編程時你只要繼續對 調用Lucas定理即可。
代碼可以遞歸的去完成這個過程,其中遞歸終點為 t = 0 ;
時間 O(log (n)*p):)
推導過程
Lucas定理證明:
首先你需要這個算式: ,其中f > 0&& f < p,然後
(1 + x) Ξ(1 + x) Ξ( (1 + x))· (1 + x)Ξ(1 + x) · (1 + x) (mod p)
所以得(1 + x)
(mod p)我們求左邊 (1 + x)中的 的係數為:
求右邊公式中的 為:
通過觀察你會發現若且唯若i = t , j = r ,能夠得到
的係數,即
所以
得證。
代碼實現
c++
求C(n, m) mod 10007
見右圖,參考馮志剛《初等數論》第37頁。